/**
 * 
 */
package model.container.edges;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

import model.Edge;

public class Fibonnacci extends Edges {
	public static class Node {
		private int children = 0;

		private Node prev;
		private Node next;
		@SuppressWarnings("unused")
		private Node parent;
		private Node child;
		
		Edge value;
		
		public Edge getValue() {
			return value;
		}
		
		public void setValue(Edge v) {
			value = v;
		}
		
		public Node(Edge v) {
			prev = next = this;
			value = v;
		}

		@Override
		public String toString() {
			return value.toString()+", children="+children;
		}
	}
	
	private Node min;
	private int size = 0;
	
	@Override
	public String toString() {
		return min.toString();
	}

	@Override
	public void addItem(Edge e) {
		Node n = new Node(e);

		//System.out.println(this.getClass()+" [+] Adding item at "+size+" : "+e);

		min = mergeL(min, n);
		size++;
	}

	@Override
	public Edge getMinimal() {
		if(isEmpty())
			throw new NoSuchElementException("Heap is empty");
		size--;
		
		//System.out.println(getClass()+" [+] Getting minimal");

		// the value to return
		Node t = min;

		// now we try to remove this element from the list of roots
		if(min.next == min)	// if t is the only element
			min = null;
		else {
			min.prev.next = min.next;
            min.next.prev = min.prev;
            min = min.next;
		}

		/*
		 * We clear the .parent of all the min's children,
		 * since they are about to become roots
		 */
		if(t.child != null) {
			Node c = t.child;
			do {
				c.parent = null;
				c = c.next;
			} while (c != t.child);
		}
		
		min = mergeL(min, t.child);
		
		// t'was a DREAM !
		if(min == null) {
			//System.out.println(getClass()+" [+] Got (1) : "+t.getValue());
			return t.getValue();
		}
		
		List<Node> trees = new ArrayList<Node>();
		List<Node> toDo = new ArrayList<Node>();
		
		for(Node c = min; toDo.isEmpty() || toDo.get(0) != c; c = c.next)
			toDo.add(c);
		
		for(Node c : toDo) {
			while(true) {
				// make sure trees is long enough to hold all of our children
				while(c.children >= trees.size())
					trees.add(null);
				
				// if nothing here, 
				if(trees.get(c.children) == null) {
					trees.set(c.children, c);
					break;
				}
				
				Node o = trees.get(c.children);
				trees.set(c.children, null);
				
				Node tMin = o.getValue().getCost() < c.getValue().getCost() ? o : c;
				Node tMax = o.getValue().getCost() < c.getValue().getCost() ? c : o;
				
				tMax.next.prev = tMax.prev;
				tMax.prev.next = tMax.next;
				
				tMax.next = tMax.prev = tMax;
				min.child = mergeL(min.child, tMax);

				tMax.parent = tMin;
				tMin.children++;

				c = tMin;
			}

			if (c.getValue().getCost() <= min.getValue().getCost())
				min = c;
        }

		//System.out.println(getClass()+" [+] Got (2) : "+t.getValue());
		return t.getValue();
	}

	@Override
	public boolean isEmpty() {
		return min == null;
	}
	
	@Override
	public int getSize() {
		return size;
	}

	/**
	 * Return a new Fibonnaci heap that contains all the elements of
	 * the two heaps.
	 * 
	 * @param a The first Fibonnaci heap to merge
	 * @param b The second Fibonnaci heap to merge
	 * @return The new Fibonnaci heap created
	 */
	public static Fibonnacci merge(Fibonnacci a, Fibonnacci b) {
		Fibonnacci n = new Fibonnacci();

		n.min = mergeL(a.min, b.min);
		n.size = a.size + b.size;
		
		a.size = b.size = 0;
		a.min = null;
		b.min = null;
		
		return n;
	}

	/**
	 * 
	 * @param a A pointer into one of the two linked lists
	 * @param b A pointer into the other of the two linked lists
	 * @return A pointer to the smallest element of the resulting list
	 */
	private static Node mergeL(Node a, Node b) {
		if(a == null || b == null)
			if(a == null && b == null)
				return null;
			else if(a == null)
				return b;
			else
				return a;

		//System.out.println(a.getClass()+" [+] Merging "+a+" with "+b);

		Node n = a.next;
		
		a.next = b.next;
        a.next.prev = a;
        b.next = n;
        b.next.prev = b;

        return a.getValue().getCost() < b.getValue().getCost() ? a : b;
	}
}
